#include <iostream>
#include<sstream>
#include <fstream>
#include <vector>
#include <random>
#include <algorithm>

using namespace std;

const int SIZE = 9;
const int EMPTY = 0;
const char EMPTY_CHAR = '$';

bool isValid(const vector<vector<int>>& board, int row, int col, int num) {
    // 检查行是否合法
    for (int c = 0; c < SIZE; ++c) {
        if (board[row][c] == num) {
            return false;
        }
    }

    // 检查列是否合法
    for (int r = 0; r < SIZE; ++r) {
        if (board[r][col] == num) {
            return false;
        }
    }

    // 检查九宫格是否合法
    int startRow = 3 * (row / 3);
    int startCol = 3 * (col / 3);
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            if (board[startRow + r][startCol + c] == num) {
                return false;
            }
        }
    }

    return true;
}

bool solveSudoku(vector<vector<int>>& board) {
    for (int r = 0; r < SIZE; ++r) {
        for (int c = 0; c < SIZE; ++c) {
            if (board[r][c] == EMPTY) {
                vector<int> nums = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
                random_device rd;
                mt19937 gen(rd());
                shuffle(nums.begin(), nums.end(), gen); // 洗牌

                for (int num : nums) {
                    if (isValid(board, r, c, num)) {
                        board[r][c] = num;
                        if (solveSudoku(board)) {
                            return true;
                        }
                        board[r][c] = EMPTY; // 恢复现场
                    }
                }
                return false;
            }
        }
    }
    return true;
}

void generateBlankCells(vector<vector<int>>& board) {
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(1, 3); // 每行挖空的格子数量范围为 1 到 3

    for (int i = 0; i < SIZE; ++i) {
        int numBlanks = dis(gen); // 当前行挖空的格子数量
        vector<int> rowIndices(SIZE);
        for (int j = 0; j < SIZE; ++j) {
            rowIndices[j] = j;
        }
        random_shuffle(rowIndices.begin(), rowIndices.end()); // 随机打乱当前行的格子索引

        for (int j = 0; j < numBlanks; ++j) {
            board[i][rowIndices[j]] = EMPTY; // 挖空格子
        }
    }
}

void writeSudokuToFile(const vector<vector<int>>& board, ofstream& file) {
    for (const auto& row : board) {
        for (int num : row) {
            if (num != EMPTY) {
                file << num << " ";
            }
            else {
                file << EMPTY_CHAR << " ";
            }
        }
        file << endl;
    }
    file << endl; // 空一行
}

void writeSolutionToFile(const vector<vector<int>>& board, ofstream& file) {
    file << "数独局面：" << endl;
    writeSudokuToFile(board, file);
    file << "解：" << endl;
    vector<vector<int>> solvedBoard = board;
    if (solveSudoku(solvedBoard)) {
        writeSudokuToFile(solvedBoard, file);
    }
    else {
        file << "数独无解" << endl;
    }
    file << endl; // 空一行
}

bool readSudokuFromFile(vector<vector<int>>& board, ifstream& file) {
    for (int r = 0; r < SIZE; ++r) {
        for (int c = 0; c < SIZE; ++c) {
            char ch;
            file >> ch;
            if (ch == EMPTY_CHAR) {
                board[r][c] = EMPTY;
            }
            else {
                board[r][c] = ch - '0';
            }
        }
    }
    string emptyLine;
    getline(file, emptyLine); // 读取空行
    return true;
}

int main() {
    int numGames;
    cout << "请输入要生成的数独局面数量：";
    cin >> numGames;

    string choice;
    cout << "是否需要生成数独局面？(Y/N): ";
    cin >> choice;

    if (choice == "Y" || choice == "y") {
        ofstream sudokuFile("sudoku.txt");
        ofstream solutionFile("solution.txt");

        if (sudokuFile.is_open() && solutionFile.is_open()) {
            random_device rd;
            mt19937 gen(rd());

            for (int game = 0; game < numGames; ++game) {
                vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));

                solveSudoku(sudoku);
                generateBlankCells(sudoku);

                writeSudokuToFile(sudoku, sudokuFile);
                writeSolutionToFile(sudoku, solutionFile);
            }

            sudokuFile.close();
            solutionFile.close();

            cout << "数独局面和解已成功写入文件" << endl;
        }
        else {
            cout << "无法打开文件" << endl;
        }
    }
    else if (choice == "N" || choice == "n") {
        ifstream sudokuFile("sudoku.txt");
        ofstream solutionFile("solution.txt");

        if (sudokuFile.is_open() && solutionFile.is_open()) {
            int game = 1;
            while (!sudokuFile.eof()) {
                vector<vector<int>> sudoku(SIZE, vector<int>(SIZE, 0));
                readSudokuFromFile(sudoku, sudokuFile);

                solutionFile << "数独局面 " << game << ":" << endl;
                writeSolutionToFile(sudoku, solutionFile);

                ++game;
            }

            sudokuFile.close();
            solutionFile.close();

            cout << "数独解已成功写入文件" << endl;
        }
        else {
            cout << "无法打开文件" << endl;
        }
    }
    else {
        cout << "无效的选择" << endl;
    }

    return 0;
}
